using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;

namespace ProjectEuler.Core.Helpers
{
    public static class MathHelper
    {
        // http://snipplr.com/view/6440/euclids-algorithm/
        // least common multiple using GCD
        public static int LCM(int a, int b)
        {
            if (a > b)
            {
                return (b/GCD(a, b))*a;
            }
            return (a/GCD(a, b))*b;
        }

        // http://snipplr.com/view/6440/euclids-algorithm/
        // euclid's alg to get gcd
        public static int GCD(int a, int b)
        {
            if(a==0)
            {
                return b;
            }
            if(b == 0)
            {
                return a;
            }
            if(a >b)
            {
                return GCD(b, a%b);
            }
            return GCD(a, b%a);
        }
        public static BigInteger GCD(BigInteger a, BigInteger b)
        {
            if(a==0)
            {
                return b;
            }
            if(b == 0)
            {
                return a;
            }
            if(a >b)
            {
                return GCD(b, a%b);
            }
            return GCD(a, b%a);
        }

        public static bool IsPrime(int n)
        {
            return IsPrime((long) n);
        }

        // this is a much faster prime number detector than the naive one
        // stolen from http://projecteuler.net/project/resources/007_c1bfcd3425fd13f6e9abcfad4a222e35/007_overview.pdf
        // but basically just takes the prime definition and a couple of other rules and applies it
        public static bool IsPrime(long n)
        {
            n = Math.Abs(n);                // doesn't seem to work well for some negative numbers...so just take abs

            // 2 is the smallest prime
            if(n==1)
            {
                return false;
            }

            // 2 and 3 are prime
            if(n<4)
            {
                return true;
            }

            // all primes are odd
            if((n % 2) == 0)
            {
                return false;
            }

            // we've already excluded 4,6,8
            if(n<9)
            {
                return true;
            }

            // we've already covered 3, so anything else divisible by 3 isn't prime
            if((n%3) ==0)
            {
                return false;
            }

            var r = Math.Floor(Math.Sqrt(n));       // sqrt(n) rounded to the greatest int r so that r*r <= n
            var f = 5;
            while(f <= r)
            {
                if((n%f) == 0)
                {
                    return false;
                }
                if((n%(f+2))==0)
                {
                    return false;
                }
                f += 6;
            }
            return true;
        }

        // this is a method for determining even which doesn't use modulus
        // is actually does save a tiny bit of time in a situation where it is used
        // a lot -- for instance, doing it 1000000 times with this method saves about 2 seconds
        public static bool IsEven(long num)
        {
            return (num & 1) == 0;
        }

        public static long PascalsTriangleGetEntry(int row, int column)
        {
            long current = 1;

            for (int i = 1; i <= column; i++)
            {
                current = (current * (row + 1 - i)) / i;
            }

            return current;
        }

        public static IList<int> FactorsOf(int n)
        {
            var factors = new List<int>();
            for (int i = 1; i * i <= n; i++)
            {
                if (n % i == 0)
                {
                    factors.Add(i);
                    if (i * i != n)
                    {
                        factors.Add(n/i);
                    }
                }
            }
            return factors;
        }

        public static BigInteger Factorial(int n)
        {
            var factorial = new BigInteger(1);
            for (int i = 1; i <= n; i++)
            {
                factorial *= i;
            }
            return factorial;
        }

        public static bool IsPandigital(int nums)
        {
            return IsPandigital(nums.ToString());
        }
        public static bool IsPandigital(long nums)
        {
            return IsPandigital(nums.ToString());
        }
        public static bool IsPandigital(string nums)
        {
            if(nums.Length > 9)
            {
                throw new ArgumentException("Pandigital numbers can't be more than 9 digits");
            }
            if(nums.Length <= 0)
            {
                return false;
            }

            var compareDigits = new StringBuilder("");
            for (int i = 1; i <= nums.Length; i++)
            {
                compareDigits.Append(i);
            }

            var t = string.Join("", nums.OrderBy(s => s));
            return t == compareDigits.ToString();
        }
        public static bool IsPandigital(string nums, string pandigits)
        {
            nums = string.Join("", nums.OrderBy(s => s));
            return nums == pandigits;
        }

        public static IList<long> PrimeFactorsOf(long n)
        {
            var factors = new List<long>();
            for (long i = 2; i <= n / i; i++)
            {
                while (n % i == 0)
                {
                    factors.Add(i);
                    n = n / i;
                }
            }
            if (n > 1)
            {
                factors.Add(n);
            }
            return factors;            
        }

        public static IEnumerable<int> GetPrimes()
        {
            yield return 2;
            int i = 1;
            while (i < int.MaxValue)
            {
                if (IsPrime(i))
                {
                    yield return i;
                }
                i += 2;
            }
        }
    }
}